package com.nowcoder.code.hjnc;

import java.util.Arrays;

public class NC88 {


    public int findKth(int[] a, int n, int K) {
        return quickSortK(a, K, 0, n - 1);
    }


    public int quickSortK(int[] is, int k, int start, int end) {
        if (start >= end) {
            return is[k - 1];
        }
        int os = start;
        int oe = end;
        int mid = is[os];

        while (start < end) {
            while (start < end && is[end] < mid) {
                end--;
            }
            while (start < end && is[start] >= mid) {
                start++;
            }
            int tmp = is[start];
            is[start] = is[end];
            is[end] = tmp;
        }

        is[os] = is[start];
        is[start] = mid;

        if (start == k - 1) {
            return is[start];
        } else if (start > k - 1) {
            return quickSortK(is, k, os, start - 1);
        } else {
            return quickSortK(is, k, start + 1, oe);
        }

    }

    public static void main(String[] args) {
        int[] is = {1332802, 1177178, 1514891, 871248, 753214, 123866, 1615405, 328656, 1540395, 968891, 1884022, 252932, 1034406, 1455178, 821713, 486232, 860175, 1896237, 852300, 566715, 1285209, 1845742, 883142, 259266, 520911, 1844960, 218188, 1528217, 332380, 261485, 1111670, 16920, 1249664, 1199799, 1959818, 1546744, 1904944, 51047, 1176397, 190970, 48715, 349690, 673887, 1648782, 1010556, 1165786, 937247, 986578, 798663};
//        int[] is = {10, 10, 9, 9, 8, 7, 5, 6, 4, 3, 4, 2};
        System.out.println(new NC88().findKth(is, is.length, 24));
        System.out.println(Arrays.toString(is));
//        NC88 nc = new NC88();
//        nc.quickSortK(is, 0, 0, is.length - 1);
//        System.out.println(Arrays.toString(is));
//        Arrays.sort(is);
//        System.out.print("[");
//        for (int i = is.length - 1; i >= 0; i--) {
//            System.out.print(is[i] + ", ");
//        }

    }

}
